package medium;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/9/9 19:33
 */
public class No33_搜索旋转排序数组 {
    public static void main(String[] args) {
        Solution33 solution33 = new Solution33();
        int[] nums = new int[]{4, 5, 6, 7, 0, 1, 2};
        int search = solution33.search(nums, 0);
        System.out.println(search);
    }
    
}

class Solution33 {
    public int search(int[] nums, int target) {
        //二分查找
        int red = 0;
        int green = nums.length - 1;
        //开始循环
        while (red <= green) {
            int yellow = (red + green) / 2;
            if (target == nums[red]) {
                return red;
            }
            if (target == nums[yellow]) {
                return yellow;
            }
            if (target == nums[green]) {
                return green;
            }
            //判断 red-yellow 是否升序
            if (nums[red] < nums[yellow]) {
                //一定升序
                //在 red-yellow中判断target
                if (target > nums[red] && target < nums[yellow]) {
                    green = yellow - 1;
                } else {
                    red = yellow + 1;
                }
            } else {
                //一定非升序
                //在 yellow-green 中判断target
                if (target > nums[yellow] && target < nums[green]) {
                    red = yellow + 1;
                } else {
                    green = yellow - 1;
                }
            }

        }
        return -1;
    }
}



    //public int search(int[] nums, int target) {
    //    //升序,互不相同 
    //    // [0,1,2,4,5,6,7] -> [4,5,6,7,0,1,2]
    //    //  [4,5,6,7,0,1,2], target = 0 -> 4
    //    //暴力循环
    //    for (int i = 0; i < nums.length; i++) {
    //        if (nums[i] == target) {
    //            return i;
    //        }
    //    }
    //    return -1;
    //}
